using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Dida
{
	/// <summary>
	/// A simple 2D polygon, of 3 or more vertices. It can be convex or concave,
	/// but should not have intersecing edges.
	/// </summary>
	public class Polygon2D
	{
		List<Vector2D> verts;

		internal Polygon2D() { }

		public Polygon2D(IEnumerable<Vector2D> srcVerts)
		{
			Debug.Assert(srcVerts != null);
			verts = new List<Vector2D>(srcVerts);
			Debug.Assert(verts.Count >= 3,"A polygon should at least have 3 vertices");
		}

		public Rect BoundingRect
		{
			get
			{
				Debug.Assert(verts.Count >= 3);

				Rect ret = new Rect(verts[0], verts[0]);
				for(int i = 0;i < verts.Count;i++)
				{
					ret.Expand(verts[i]);
				}
				return ret;
			}
		}

		private enum LineSide
		{
			Above,
			OnLine,
			Below,
		}
		private static LineSide GetLineSide(float y)
		{
			if (y < -.001f)
				return LineSide.Above;
			else if (y > .001f)
				return LineSide.Below;
			else
				return LineSide.OnLine;
		}

		public bool PointInPolygon(Vector2D pt)
		{
			Debug.Assert(verts.Count >= 3);

#if !(SECURE || DEBUG)
			unsafe
			{
#endif
				int numVerts = verts.Count;

#if SECURE || DEBUG
				Vector2D[] vertDists = new Vector2D[numVerts];
#else
				Vector2D* vertDists = stackalloc Vector2D[numVerts];
#endif
				for (int i = 0; i < numVerts; i++)
				{
					vertDists[i] = verts[i] - pt;
				}

				// find a start vert that's does not lay on the line.
				LineSide startSide = LineSide.OnLine;	// just assign it to surpress a warning
				int loopStart = -1;
				for (int i = 0; i < numVerts; i++)
				{
					startSide = GetLineSide(vertDists[i].y);
					if (startSide != LineSide.OnLine)
					{
						loopStart = i;
						break;
					}
				}

				if (loopStart == -1)
				{
					// the whole polygon is so damn small, 
					// that floating point inaccuracy prevents us from doing
					// a real test, so we will just return no intersection
					return false;
				}

				int loopEnd = loopStart + numVerts;
				LineSide lastNotOnLineSide = startSide;

				bool intersect = false;

				for (int i = loopStart; i < loopEnd; i++)
				{
					int startVert = i % numVerts;
					int endVert = (i + 1) % numVerts;

					LineSide endSide = GetLineSide(vertDists[endVert].y);

					if (
						// if true, this edge doesn't even cross the infinite line, 
						// so it can't be interesting
						endSide == lastNotOnLineSide ||
						
						// if true, the end vertex is on the line, so we'll postpone the check to 
						// when the edges will leave the line.
						endSide == LineSide.OnLine)
					{
						
						startSide = endSide;
						continue;
					}


					if (startSide == LineSide.OnLine)
					{
						// if we get here, this test:
						//   endSide != lastNotOnLineSide)
						// is true for sure, because otherwise, we wouldn't
						// have passed the endSide == lastOnLineSide test
						// earlier on

						// the intersection point is the start vertex,
						// which layed on the line.
						if (vertDists[startVert].x < 0)
						{
							intersect = !intersect;
						}
					}
					else
					{
						float edgeLeft;		// the left bound of the edge
						float edgeRight;		// the right bound of the edge
						if (vertDists[startVert].x > vertDists[endVert].x)
						{
							edgeLeft = vertDists[endVert].x;
							edgeRight = vertDists[startVert].x;
						}
						else
						{
							edgeLeft = vertDists[startVert].x;
							edgeRight = vertDists[endVert].x;
						}

						if (edgeLeft > 0)
						{
							// the whole edge is at the right side of the point, 
							// so it can't intersect the segment of the line
						}
						else if (edgeRight < 0)
						{
							// it intersects for sure.
							intersect = !intersect;
						}
						else
						{
							// calculate the intersection point, to see if the edge
							// intersects the line
							float intersectionParam = -vertDists[startVert].y /
								(vertDists[endVert].y - vertDists[startVert].y);
							float intersectionX = vertDists[startVert].x +
								intersectionParam * (vertDists[endVert].x - vertDists[startVert].x);
							if (intersectionX < 0)
							{
								// the point where the inf line and the edge intersect, is
								// at the left of the test point, so the edge
								// actually intersects the line segment.

								intersect = !intersect;
							}
						}
					}

					lastNotOnLineSide = startSide = endSide;
				}

				return intersect;
#if !(SECURE || DEBUG)
			}
#endif
		}
	}
}